package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;


    /* 
        定义根节点t0为初始化扩展节点
        根节点t0入队
        while(队不空)
        {
            出队 --t;
            for (j = r0; j < rn; ++j)
            {
                对t利用规则j发展新节点tj;
                利用限界函数判断tj是否可行;
                if (可行)
                {
                    若是目标解，找到结果，return
                    否则，进队
                }
            }
        }
    
    */
public class Pra11 {
    //每个皇后节点应该要保存之前他所含有的皇后位置信息
    class Queen {
        int level;
        int position;
        List<Integer> pre;

        public Queen(int level, int position) {
            this.level = level;
            this.position = position;
            this.pre = new LinkedList<>();
        }
    }

    public boolean check(Queen last, int j) {
        int l = last.level + 1; //这一层的层数
        List<Integer> pre = last.pre;
        for (int i = 0; i < pre.size(); i++) {
            if (j == pre.get(i) || Math.abs(i - l) == Math.abs(pre.get(i) - j))
                return false;
        }
        return true;
    }

    public void nQueen(int n) {
        // Queen head = new Queen(-1, Integer.MAX_VALUE);
        Queue<Queen> qs = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            Queen t = new Queen(0, i);
            t.pre.add(i);
            qs.offer(t);
        }
        List<List<String>> res = new ArrayList<>();
        int m, level = 1;
        Queen cur;
        while (!qs.isEmpty()) {
            m = qs.size();
            for (int j = 0; j < m; j++) { //一次检查完一层的节点。
                cur = qs.poll();
                for (int i = 0; i < n; i++) {
                    if (check(cur, i)) {
                        Queen t = new Queen(cur.level + 1, i);
                        t.pre = new ArrayList<>();
                        t.pre.addAll(cur.pre);
                        t.pre.add(i); //保存之前节点的位置信息和自己的位置信息
                        qs.offer(t);
                    }
                }
            }
            level++;
            if (level == n) {
                while (!qs.isEmpty()) {
                    cur = qs.poll();
                    List<String> list = new ArrayList<>();
                    for (int i = 0; i < cur.pre.size(); i++) {
                        StringBuilder sb = new StringBuilder();
                        for (int j = 0; j < n; j++) {
                            if (cur.pre.get(i) == j) {
                                sb.append("Q");
                            } else {
                                sb.append("*");
                            }
                        }
                        list.add(sb.toString());
                    }
                    res.add(list);
                }
                break;
            }
        }
        System.out.println(res);
    }
    @Test
    public void test() {
        nQueen(4);    
        nQueen(5);        
        nQueen(6);               
    }

/* 
    //分支限界法n皇后
    class Queen {
        int level; //节点所在层数
        int position; //所在的棋盘位置[0...n-1]
        LinkedList<Queen> pre;
        public Queen(int level, int position) {
            this.level = level;
            this.position = position;
            pre = new LinkedList<>();
        }
    }

    public void nQueue(int n) {
        Queue<Queen> qs = new LinkedList<>();
        Queen cur;
        LinkedList<Queen> board = new LinkedList<>();
        int t;
        for (int i = 0; i < n; i++) { //初始拓展节点
            cur = new Queen(0, i);
            qs.offer(cur);
            board.add(cur);
            int idx = 1;
            while (!qs.isEmpty()) {
                //一次探查一个节点的方案
                cur = qs.poll();
                for (int j = 0; j < n; j++) {
                    if (check(board, j)) {
                        qs.offer(new Queen(idx, j));
                    }
                }
                idx++;
            }
        }
        
    }

    public boolean check(LinkedList<Queen> board, int p) {
        Queen cur;
        int n = board.size();
        for (int i = 0; i < board.size(); i++) {
            cur = board.get(i);
            if (cur.position == p || Math.abs(i - n) == Math.abs(p - cur.position)) {
                return false;
            }
        }
        return true;
    } */
}
